package search;

import java.util.ArrayList;
import java.util.List;

/**
 * 二分查找
 */
public class BinarySearch {

  public static void main(String[] args) {

    int[] array={1,2,3,4,4,4,4,5,6,7,8,9};
    List<Integer> list = binarySearch2(array, 0, array.length - 1, 4);
    System.out.println(list);
  }

  private static int binarySearch(int[] array, int left, int right, int value) {

    if (left>right){
      return -1;
    }
    int mid=(left+right)/2;
    int midValue=array[mid];
    if (value<midValue){
      return binarySearch(array,left,mid-1,value);
    }else if (value>midValue){
      return binarySearch(array,mid+1,right,value);
    }else {
      return mid;
    }

  }

  private static List<Integer> binarySearch2(int[] array, int left, int right, int value) {
    if (left>right){
      return new ArrayList<Integer>();
    }
    int mid=(left+right)/2;
    int midValue=array[mid];
    if (value<midValue){
      return binarySearch2(array,left,mid-1,value);
    }else if (value>midValue){
      return binarySearch2(array,mid+1,right,value);
    }else {
      ArrayList<Integer> list = new ArrayList<>();
      int temp=mid-1;
      while (temp>=left&&midValue==array[temp]){
        list.add(temp);
        temp--;
      }
      list.add(mid);

      temp=mid+1;
      while (temp<=right&&midValue==array[temp]){
        list.add(temp);
        temp++;
      }
      return list;
    }
  }
}
